public class BSTree<T extends Comparable<T>> {

    public class BSNode<T extends Comparable<T>> {
        T key;
        BSNode<T> left;
        BSNode<T> right;
        BSNode<T> parent;

        public BSNode(T key, BSNode<T> left, BSNode<T> right, BSNode<T> parent) {
            this.key = key;
            this.left = left;
            this.right = right;
            this.parent = parent;
        }
    }

    private BSNode<T> mRoot;

    private void preOrder(BSNode<T> tree) {
        if (tree != null) {
            System.out.println(tree.key + " ");
            preOrder(tree.left);
            preOrder(tree.right);
        }
    }

    public void preOrder() {
        preOrder(mRoot);
    }

    private void inOrder(BSNode<T> tree) {
        if (tree != null) {
            inOrder(tree.left);
            System.out.println(tree.key + " ");
            inOrder(tree.right);
        }
    }

    public void inOrder() {
        inOrder(mRoot);
    }

    private void postOrder(BSNode<T> tree) {
        if (tree != null) {
            postOrder(tree.left);
            postOrder(tree.right);
            System.out.println(tree.key + " ");
        }
    }

    public void postOrder() {
        postOrder(mRoot);
    }

    private BSNode<T> search(BSNode<T> x, T key) {
        if (x == null) {
            return x;
        }
        int cmp = key.compareTo(x.key);
        if (cmp < 0) {
            return search(x.left, key);
        } else if (cmp > 0) {
            return search(x.right, x.key);
        } else {
            return x;
        }
    }

    public BSNode<T> search(T key) {
        return search(mRoot, key);
    }

    private BSNode<T> iteratorSearch(BSNode<T> x, T key) {
        while (x != null) {
            int cmp = key.compareTo(x.key);
            if (cmp < 0) {
                x = x.left;
            } else if (cmp > 0) {
                x = x.right;
            } else {
                return x;
            }
        }
        return x;
    }

    public BSNode<T> iteratorSearch(T key){
        return iteratorSearch(mRoot,key);
    }

    private BSNode<T> maximum(BSNode<T> tree){
      while(tree.right!=null){
          tree = tree.right;
      }
      return tree;
    }

    public T maximum(){
        BSNode<T> p = maximum(mRoot);
        if(p!=null){
            return p.key;
        }
        return null;
    }

    private BSNode<T> minimum(BSNode<T> tree){
        while(tree.left!=null){
            tree = tree.left;
        }
        return tree;
    }

    public T minimum(){
        BSNode<T> p = minimum(mRoot);
        if(p!=null){
            return p.key;
        }
        return null;
    }


    public BSNode<T> predecessor(BSNode<T> x){
        if(x.left!=null){
            return maximum(x.left);
        }

        BSNode<T> y = x.parent;
        while (y!=null&&(x == y.left)){
            x = y;
            y = y.parent;
        }
        return y;
    }


    public BSNode<T> successor(BSNode<T> x){
        if(x.right!=null){
            return minimum(x.right);
        }

        BSNode<T> y = x.parent;
        while(y!=null&&(x == y.right)){
            x = y;
            y = y.parent;
        }
        return y;
    }


    private void insert(BSTree<T> bst,BSNode<T> z){
         int cpm;
         BSNode<T> y = null;
         BSNode<T> x = bst.mRoot;

         while(x!=null){
             y = x;
             cpm = z.key.compareTo(x.key);
             if(cpm<0){
                 x = x.left;
             }else{
                 x = x.right;
             }
         }

         z.parent = y;
         if(y==null){
             bst.mRoot = z;
         }else{
             cpm = z.key.compareTo(y.key);
             if(cpm<0){
                 y.left = z;
             }else{
                 y.right = z;
             }
         }
    }


    public void insert(T key){
        BSNode<T> z = new BSNode<>(key,null,null,null);
        insert(this,z);
    }


    private BSNode<T> remove(BSTree<T> bst,BSNode<T> node){
          if(node.left!=null&&node.right!=null){
              BSNode<T> successor  = successor(node);
              node.key = successor.key;
              node = successor;
          }

          BSNode<T> child = null;
          if(node.left!=null){
              child = node.left;
          }else if(node .right!=null){
              child = node.right;
          }

          if(child!=null){
              child.parent = node.parent;
          }

          if(node.parent == null){
              bst.mRoot = child;
          }else if(node == node.parent.left){
              node.parent.left = child;
          }else if(node == node.parent.right){
              node.parent.right = child;
          }

          return node;
    }



}
